#define _CRT_SECURE_NO_WARNINGS 1
class Solution{
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size();
        vector<vector<bool>> dp(n1 + 1, vector<bool>(n2 + 1, false));
        s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;
        for (int i = 0; i <= n1; i++) if (s1[i] == s3[i]) dp[i][0] = true; else break;
        for (int j = 0; j <= n2; j++) if (s2[j] == s3[j]) dp[0][j] = true; else break;
        for (int i = 1; i <= n1; i++)
            for (int j = 1; j <= n2; j++)
                dp[i][j] = (s1[i] == s3[i + j] ? dp[i - 1][j] : false) || (s2[j] == s3[i + j] ? dp[i][j - 1] : false);

        return dp[n1][n2];
    }
};